package leetcode_700;

import java.util.Arrays;

/**
 *@author 周杨
 *ValidTriangleNumber_611 给定一个数组 找出所有能构成三角形的排列数量
 *describe:用回溯AC 2% 用双指针 AC 80%
 *2018年9月19日 上午10:56:12
 */
public class ValidTriangleNumber_611 {
	
	public static void main(String[] args) {
		ValidTriangleNumber_611 test=new ValidTriangleNumber_611();
		test.triangleNumber(new int[] {2,2,3,4});
	}
	
	/**
	 * describe:双指针
	 * 2018年9月19日 上午10:57:25
	 */
	public int triangleNumber(int[] nums) {
        if (nums == null || nums.length < 3)
            return 0;
        Arrays.sort(nums);
        int res = 0;
        for (int i = nums.length - 1; i > 0; i--){
            int l = 0, r = i - 1;
            while (l < r){
                if (nums[l] + nums[r] > nums[i]){//如果连最小的l都与r加起来大于i 那么大于l的也行
                    res += r-l;//中间的都可行
                    r--;
                }
                else 
                    l++;
            }
        }
        return res;
    }
	
	int []nums;
	int res=0;
	/**
	 * describe:回溯 效率太慢
	 * 2018年9月19日 上午10:57:15
	 */
	public int triangleNumber1(int[] nums) {
		if(nums.length<3)
			return 0;
		Arrays.sort(nums);
        this.nums=nums;
        for(int i=0;i<nums.length-2;i++) {
        	help(i,i+1,i+2);
        }
        return this.res;
    }
	
	public void help(int i,int j,int k) {
		if(j>=nums.length)
			return ;
		if(k>=nums.length) {
			help(i,j+1,j+2);
			return ;
		}
		if(nums[i]+nums[j]>nums[k]) {
			++this.res;
			help(i,j,k+1);
		}
		else
			help(i,j+1,j+2);
	}
}
